1. Field of the Invention
The present invention relates to data transfer within logical channels by a node in a telecommunications system, and, in particular, generating a sequence of logical channels for service by the node.
2. Description of the Related Art
Telecommunication systems typically employ a multiplexing hierarchy to integrate multiple user data channels for transmission through a medium. Transmission through the medium at one level of the hierarchy is generally at a much higher rate than the rate of each user""s data at a lower level of the hierarchy. For synchronous networks, the methods employed for multiplexing may use a frame format in which data of individual user channels are inserted into predefined xe2x80x9ctimeslotsxe2x80x9d within a frame. Some networks have rather rigid provisioning for channel-timeslot allocation, such as time-division multiplexing, while others, such as synchronous packet (cell) networks, may allocate channels within the various timeslots with greater flexibility. Each frame at one level may be inserted into one or more timeslots of a frame of the next, higher level of the hierarchy, thus preserving the framing and other format information of the lower level. Alternatively, a frame at the lower level may be de-multiplexed and the user channels of its timeslots then re-multiplexed into the frame at the higher level.
Many standards exist that define such multiplexing hierarchies. For example, the Synchronous Digital Hierarchy (SDH) and the Synchronous Optical Network (SONET) models are employed for optical transmission systems. In SONET, the basic frame is a synchronous transport signal at level 1 (STS-1) that comprises 810 octets of data (27 octets overhead and 783 octets payload). Higher levels (STS-n) are formed from predefined multiples of n times the basic STS-1 frame. In general, SONET frames map directly to optical carrier (OC) line signals used for physical transmission through a line (i.e., STS-1 maps directly to OC-1, STS-48 maps directly to OC-48, etc.) Similarly, in SDH the basic frame is a synchronous transmission module at level 1 (STM-1) that comprises 2430 octets of data (81 octets overhead and 2349 octets payload). Higher levels (STM-n) are formed from predefined multiples of n times the basic STM-1 frame. Many standards are related. For example, the STM-1 frame may be formed from 3 STS-1 frames. Thus, a certain SDH level may be mapped to a corresponding STS level, such as STM-1 mapped directly to STS-3and STM-16 mapped directly to STS-48. However, only predefined multiples are allowed by the standards.
FIG. 1 illustrates a transmission format of a prior art data frame for STS-48 (or OC-48) payload that may be employed for multiplexing several channels within a sequence of timeslots. As illustrated in FIG. 1, the payload is organized into four rows of 12 timeslots. Also shown in FIG. 1, each user data stream (e.g., d0 and d1, sometimes referred to as xe2x80x9clogical channelsxe2x80x9d) may occupy several different timeslots within a given frame. A payload mark may be included within the frame and may be used to identify whether the bits within a frame are valid information or are blank/unused/undefined bits. External header or other control information may be used to identify user or other provisioning information.
A user""s communication path through a network comprises those nodes and links through which the user data stream traverses. Nodes may contain switching, multiplexing/demultiplexing, and/or other line terminal equipment; and links may be those physical lines or media that connect the equipment. Once provisioned through the network, a logical channel through the path may be identified at any given time by the timeslot position(s) within a frame at each level. At any given node of a network through which the user communication path traverses, several processing functions may be applied to a link carrying the user""s logical channel. These processing functions may be employed for switching and cross-connect (e.g., cell-relay) operations, or may be employed for re-formatting operations (e.g., convert between DS-3, SONET, SDH, and UTOPIA frame formats).
Three common processing functions are drop-add, cross-connect, and rearrangement/packing. For drop-add, a logical channel is either xe2x80x9cdroppedxe2x80x9d or xe2x80x9caddedxe2x80x9d to a frame. A drop may be for local reception from frames of one line input to (output from) the node. An add may be for local transmission to frames of one line output from the node. For cross-connect, a logical channel is transferred between timeslots of two or more different frames and/or lines passing through the node. For packing, the positions of timeslots allocated to user data of a logical channel are rearranged. Packing may be employed when a logical channel occupies several timeslots in positions disbursed through a frame, and rearrangement may allow for contiguous timeslots throughout the frame.
Terminal or other transmission equipment generally includes an interface to receive, buffer, and output logical channels of an input line with a given line format (hierarchical-level frame format). FIG. 2 shows a block diagram of a prior art terminal 201 that receives, buffers and outputs data of logical channels for the sequence of timeslots for the frame format shown in FIG. 1. The interface 201 includes input line termination 202, first-in, first-out (FIFO) buffers 203(0)-203(N), token ring 204, output line termination 212, and processor 205. Processor 205 may be used to coordinate or otherwise control operation of the various elements within terminal 201. Line termination 202 separates, for example, the 48 separate timeslots of the STS-48 frame while also removing header and frame format information that may be provided to processor 205. Each of N+1 logical channels is assigned to a corresponding one of the FIFO buffers 203(0)-203(N). Data for each of the N+1 logical channels that is received by input line termination 202 in one or more of the 48 timeslots is transferred to a corresponding one of the FIFO buffers 203(0)-203(N).
To generate an output OC-48 line optical signal from output line termination 212, data of each logical channel that is buffered in FIFO buffers 203(0)-203(N) is read out into one or more timeslots of the OC-48 frame that is generated by output line termination 212. Token ring 204 services, in sequence, each of the FIFO buffers 203(0)-203(N) (and hence, the sequence of logical channels) by examining the buffer to see if it is empty, processes non-empty buffers until a specified event is detected, and then examines the next buffer in the sequence. The sequence is considered xe2x80x9ctoken ringxe2x80x9d (also referred to as xe2x80x9cround-robinxe2x80x9d) scheduling since token ring 204 processes buffers in ascending or descending order, and returns to the first buffer in the sequence after the last buffer in the sequence is served. As each one of the non-empty FIFO buffers 203(0)-203(N) is served, data in the serviced buffer is inserted into the timeslot(s) of the output frame until either of two types of events first occurs. The first type of event occurs when the currently serviced FIFO buffer becomes empty. The second type of event is that a timer (not shown) generates an interrupt causing the token ring 204 to advance to the next FIFO buffer in the sequence. Timer-generated interrupts may be used to introduce xe2x80x9cfairnessxe2x80x9d to service of buffers. In either case, however, FIFO buffers 203(0)-203(N) may or may not have buffered data.
Token rings of the prior art step through each logical channel to examine each corresponding buffer before determining whether the buffer needs service, wasting processing cycles. In addition, implementations of token rings of the prior art may not be robust to corruption of the token. Consequently, the token may be xe2x80x9clostxe2x80x9d, causing the scheduler to fail. To correct this, some implementations of the prior art may include additional circuitry or logic to prevent circuit failure from corruption of the token.
The present invention relates to channel sequencing for round-robin scheduling of service for buffers associated with logical channels to transfer data, if present, in each buffer to one or more output frames while avoiding empty buffers. Channel sequencing generates a (N+1)-bit binary word, termed a channel service request (CSR) word, with each bit of the CSR word corresponding to one of (N+1) buffers and indicating whether the buffer contains data and requests service. Channel sequencing for round-robin scheduling identifies buffers for service in ascending or descending order of non-empty buffers, accounting for CSR bits set for newly filled buffers with a mask. A cycle of the round-robin scheduling begins when a CSR word is generated having at least one bit set, indicating that at least one logical channel buffer requests service. For each subsequently generated CSR word, the CSR word is combined with a mask to form a masked CSR word. The mask resets those bits of the CSR word that represent newly filled buffers for logical channels whose service is scheduled for the next cycle of round-robin scheduling. The first set of bits of the masked CSR word identifies the next, non-empty buffer for service. The mask generator employs the current masked CSR word to generate the next mask when service of the current logical channel service request completes. The cycle ends when service of the buffer corresponding to the final logical channel service request is complete, at which point round-robin scheduling rolls over to the beginning of the next cycle with the current CSR word.
In accordance with embodiments of the present invention, data is routed from an input frame to an output frame with a scheduler that implements round-robin channel sequencing based on a logical channel order. Data is received in a plurality of buffers, each buffer associated with a logical channel and receiving data for the corresponding logical channel in the input frame, wherein, when the one or more of the plurality of buffers are serviced, the data from the one or more buffers is transferred in accordance with a logical channel order for inclusion in the output frame. A channel service request (CSR) word is generated from the plurality of buffers, each bit of the CSR word associated with a channel to identify each corresponding non-empty buffer. The scheduler 1) generates a mask related to a token for round-robin scheduling; 2) generates the logical channel order from the channel service data in accordance with the round-robin scheduling; and 3) updates the logical channel order and mask during a cycle. The scheduler generates the logical channel order to select channels with non-empty buffers for service during each cycle of round-robin scheduling, and updates the mask to maintain the token.